package 剑指offer;

import common.TreeNode;

/**
 * @author zhangmin
 * @create 2021-11-17 15:54
 *
 * 7、搜索和回溯
 */
public class day7_26_27_28 {

    /**===========================================================================================================================
     * 剑指 Offer 26. 树的子结构
     * 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)，B是A的子结构， 即 A中有出现和B相同的结构和节点值。
     * 递归，判断当前节点是否和B的当前节点相同，相同则继续判断当前节点的左子树和B的左右子树是否相同结构，
     * 1、先序遍历树 A中的每个节点 An；（对应函数 isSubStructure(A, B)）
     * 2、判断树 A 中 以 An为根节点的子树 是否包含树 B 。（对应函数 recur(A, B)）
     * */
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        //先序遍历A中的每个节点
        if (A==null||B==null) return false;
        return backtrack(A,B)||isSubStructure(A.left,B)||isSubStructure(A.right,B);
    }
    //backtrack返回A为根节点的子树是否包含B
    public boolean backtrack(TreeNode A,TreeNode B){
        //当节点 B 为空：说明树 B 已匹配完成（越过叶子节点），因此返回 true ；
        if (B==null) return true;
        //当节点 A 为空：说明已经越过树 A 叶子节点，即匹配失败，返回 false；当节点 A和 B 的值不同：说明匹配失败，返回 false ；
        if (A==null||A.val!=B.val) return false;
        return backtrack(A.left,B.left)&&backtrack(A.right,B.right);
    }

    /**===========================================================================================================================
     * 剑指 Offer 27. 二叉树的镜像
     * 请完成一个函数，输入一个二叉树，该函数输出它的镜像。
     * 递归将每个子树先交换左右，一层一层向上
     * */
    public TreeNode mirrorTree(TreeNode root) {
        //base case
        if (root==null) return null;
        //递归先将子树分别镜像处理
        TreeNode left = mirrorTree(root.left);
        TreeNode right = mirrorTree(root.right);
        //交换root的左右子树
        root.left=right;
        root.right=left;
        return root;
    }

    /**===========================================================================================================================
     * 剑指 Offer 28. 对称的二叉树
     * 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的
     * 递归：对于一个根节点，要判断是否是对称的，先判断左右节点值是否相等，在判断左右节点是否对称，即
     * root.left.left=root.right.right,
     * root.left.right=root.right.left
     * */
    public boolean isSymmetric(TreeNode root) {
        //base case
        if (root==null) return true;
        return helper(root.left,root.right);
    }
    //辅助方法，递归判断两颗子树是否相同
    boolean helper(TreeNode left,TreeNode right){
        if (left==null&&right==null) return true;
        if (left==null||right==null||left.val!=right.val) return false;
        return helper(left.left,right.right)&&helper(left.right,right.left);
    }


}
